<html>
<head><title>����</title></head>
<body>
<center>
    <table width=780 border=0 cellpadding=3 cellspacing=0>
        <tr>
            <td style='line-height:150%;font-size:16px;text-indent: 20'>
                <p><a href="readme.htm">����</a></p>

                <p align=center><b>�����£���ɢ���е�ֱ������㷨</b></p>

                <p align=center>�?ΰ 2008-12-2 ������ʮ��</p>

                <p><b>���������</b>��֪�Ŵ�˷�ձ?����ҵ�һ��ֱ�� y(x) = k��x + b
                    ���˷�ձ?Ȼ����[y(x)]��ʾ˷�գ�x��ʾ˷������(x=0,1,2����)��k��b�Ǵ���ϵ��</p>

                <p><b>��ѧģ�ͣ�</b>��ĳһ��ʵ�����ɢ�������D(x)������x = 0,1,2�����������һ��ֱ�� y(x) = k��x + b��ʹy(x)�� x =
                    0,1,2������ֵ��ʵ��ֵ���������0С��a�������������⣬aȡֵΪ1���ź�����������ⲻ��ʹ����С���˷�ֱ����⣬���ǿ��������
                </p>

                <p><b>��ѧģ�͵�ͼ������</b>��</p>

                <p align=center><img src=img/a001.gif></p>

                <p>ͼ��D(x)����֪����ɢ���У�E(x)= D(x)+ a�����ֱ��Ϊy = k��x + b���ҳ��ʵ���k��bʹ��ֱ��y(x)��ȫ�����ɫ����</p>

                <p><b>����˼·��</b></p>

                <p>��1��y(x)��δ֪�ģ���ȡ��k��b�Ĺ�ֵ����ͼ��ʾ�⣬��ȡk=1��b=0��Ϊ��ʼ��ֵ��</p>

                <p>
                    ��2����b��ֵ��ƽ��ֱ�ߣ��ı�bֵ����ֱ��ֱ��ȫ�������D(x)����bֵΪb1ʱ�պó������еĵ㣬�����ٽ糬��ĵ���D(x1)������ƽ�ƣ��ҵ�ֱ�߸պ�ȫ��С��E(x)ʱb��ȡֵ����Ϊb2��</p>

                <p>���b2&gt;b1����Ȼ�н⣬��kֵ���ֲ��䣬bȡֵ��b1+b2��/ 2����ôb��������Ϊh = ��b2-b1��/2�����ҹ�̽������b2&lt;=b1��������²��ۡ�</p>

                <p>
                    ��3����k��ֵ���Ե�D(x1)Ϊ�̶�����תֱ�ߣ��ҳ�ֱ�߲�����E(x)ʱk��ȡֵ��Χ��k1��k2�������k2&lt=k1���޽⣬���ҹ�̽������kȡ��k1+k2��/
                    2��</p>

                <p>
                    ��4���ӵ�2����ʼ�ظ����Ϲ�̣�ֱ���ɹ�Ϊֹ���ظ��Ĺ���У�k��ȡֵ����ԭ�л��Ͻ�һ����С��Χ�ġ����磬��һ�εõ�k�ķ�Χ��1��2֮�䣬�ڶ���Ϊ1.5��3֮�䣬��ôk��ȡֵ����ȡǰ��Ҳ����ȡ���ߣ�����ȡ���ߵĽ�����1.5��2�����������Ϲ����k��ȡֵ�޷���������Ч��Χ֮�ڣ������ѭ�����Ҳ����⡣��ʵ����D(x)�е�����һ��Ϊ�̶��㣬�����Եõ�k�����½�ֵk1��k2������һ���ܹ�ͨ������ֱ�ߣ���Ȼ�ܹ���������k1��k2��Լ��</p>

                <p>���ϵ�ȡ��b��������ֵh�����b���䣬k��������Ϊb/N��ʽ��NΪD(x)���е��ܸ���</p>

                <p><b>�㷨ʵ�֣�</b></p>

                <p>��f(x) = D(x) - y(x)����K(n��m)��ʾ��E(n)����D(m)���ߵ�б�ʡ�</p>

                <p>��ôf(x)��ʾy(x)��D(x)��������룬f(x)+a��ʾy(x)��E(x)������롣</p>

                <p>��1����ȡ��k��b�ĳ�ʼ��ֵ����k���ܵ�ȡֵ��ΧΪ��k1,k2���������ΧҪ�㹻��</p>

                <p>��2����x=0��1��2�����ϱ���f(x)�����f(x)�����ֵf1����Сֵf2����Ӧ��xֵx1��x2����ôf2+a����f(x)+
                    a����Сֵ��Ҳ����˵f2+a��y(x)��E(x)����С������롣</p>

                <p>��3�����f1&lt;f2+a���н⣬b = b + (f2+a+f1)/2��h = (f2+a-f1)/2����������������</p>

                <p>��4����x&gt;x1�ϱ���K(x��x1)��ȡ����Сֵk1������С�������ԭ����k1��ҪС�������㣩</p>

                <p>�� ����x&lt;x1�ϱ���K(x��x1)��ȡ�����ֵk2��������ֵ���ԭ����k2��Ҫ�󣬷����㣩</p>

                <p>�� �����k1&gt;=k2���޽⣬����޽ⱨ�棬����������ȡk = (k1+k2)/2��</p>

                <p>��5���ӵ�2����ʼ�ظ����㣬ֱ���н⡣ע�⣬
                    k1��k2��ȫ����е���ֵ������ĳһ�α������е���ֵ��ͨ��1��6�ξ��ܵõ��������ظ�����10�����޽⣬����ҲӦ����</p>

                <p><b>�Ż��㷨��</b></p>

                <p>��ʱ���ǲ����ˣ�������Եõ�����������ֱ�ߣ���h��ֵ�ǳ�С������õ�h = 0.000002����N =
                    10000����ôk��������Ϊ0.0000000002��Ҳ����˵k����ȡ10λ��ЧС��ſɱ�֤������ȷ�ԡ������б�Ҫ���h��ֵ�������������������hֵ�ķ�����</p>

                <p>
                    ����ǰ���ʵ���Сa��ʹ����ͼ�ĺ�ɫ�����С��Ȼ���k��b��h�����k��b�н⣬��ô��Ӧ��y(x)����ͨ��ԭ���ϴ�ĺ�ɫ��������b��ȡֵ��Χ�ͱ�ÿ�ԣ�ˣ�h��Ȼ�ͱȽϴ��ˡ���a��ԭֵ��ΪA����ôֻ�轫�����㷨��3����Ϊ�������f1&lt;f2+a���н⣬b
                    = b + (f2+A+f1)/2��h = (f2+A-f1)/ 2�����������������ȼ��ڡ����f1&lt;f2+a���н⣬h = (f2+A-f1)/2��b =
                    b+f1+h����������������</p>

                <p>
                    ��Ȼ��a��ֵҲ���ܼ�С��ࡣ��ΪĳЩ���ж����ֱ��Ҫ��ǳ����̣������Ͽ��ҵ���hֵ����ͷǳ�С������a��С����������޽⡣����������ĸ�������У���С��ȡֵ0.0002��</p>


                <p><b>�������</b></p>
                <hr style='height=1;color:#FF0000'>
                <p align=center><b><i>���֮ǰ���趨�����Ա�������С�</i></b><br>
                    D(x)������ɲ���
                    k=<input type=text id=Ck value='29.5306' size=10>
                    b=<input type=text id=Cb value='0.35789' size=10>
                    N=<input type=text id=Cn value='3000' size=10><br>
                    ���ǰ�ĳ�ʹ��ֵ��
                    k=<input type=text id=Ck0 value='29.5' size=10>
                    b=<input type=text id=Cb0 value='0' size=10>
                    a=<input type=text id=Ca0 value='0.99998' size=10><br><br>
                    ���<input type=text id=Cjg value='' size=60>
                    <input type=button onclick='test()' value='��ʼ���'>
                </p>
                <hr style='height=1;color:#FF0000'>


                <p id=progText></p>

                <script language=javascript>
                    function nihe(r, k, b, a) {
                        //��ڲ�����ϼ���,k��bΪ��ʼ��ֵ,rΪ��������,aΪ�����ߵ������
                        //����ʱ�ɰ�aֵ�ſ��Ա㷢�����⣬ȡֵa=1+1e-7���ɿ������ȡa=1-2e-4��
                        var i, kk, v, A = 1;
                        var k1 = k - 1, k2 = k + 1, f1, f2, x1;
                        for (kk = 0; kk < 10; kk++) { //���Ҵ���
                            f1 = -1e9, f2 = 1e9, x1 = -1;
                            for (i = 0; i < r.length; i++) {
                                v = r[i] - (k * i + b);     //ֱ������Ҫƽ�Ƶ���
                                if (v > f1) f1 = v, x1 = i;
                                if (v < f2) f2 = v;
                            }
                            if (f2 + a - f1 > 0) {
                                r.gh = (f2 + A - f1) / 2;
                                b += f1 + r.gh;
                                r.gk = k;
                                r.gb = b;
                                return "ok";
                            }
                            for (i = 0; i < r.length; i++) { //���µ���k��ֵ
                                if (i == x1) continue;
                                v = ( r[i] + a - r[x1] ) / (i - x1);
                                if (i < x1 && v > k1) k1 = v;
                                if (i > x1 && v < k2) k2 = v;
                                if (k1 > k2) return "�޽�";
                            }
                            k = (k1 + k2) / 2;
                        }
                        return "����" + kk + "��δ�ҵ���";
                    }
                    progText.innerText = '��Ϻ���Դ����\r\n' + nihe;

                    function test() {
                        var i, Dx = new Array();
                        var k = Ck.value - 0, b = Cb.value - 0, N = Cn.value - 0;
                        for (i = 0; i < N; i++) Dx[i] = Math.floor(i * k + b); //�������

                        var k0 = Ck0.value - 0, b0 = Cb0.value - 0, a0 = Ca0.value - 0;
                        Cjg.value = nihe(Dx, k0, b0, a0);
                        if (Cjg.value == 'ok') Cjg.value = 'k=' + Dx.gk + ' b=' + Dx.gb + ' h=' + Dx.gh;
                    }
                </script>


            </td>
        </tr>
    </table>
</center>
</body>
</html>
